/**
 * 希尔排序
 */
public class ShellSort {

    // 希尔排序，对h有序数组进行插入排序
    // 逐渐缩小h， 最后h=1时，完成整个数组的升序
    // public void sort(int[] nums) {
    //     int n = nums.length;
    //     // 使用的生成函数为2^(k - 1)
    //     // 即h = 1, 2, 4, 8...
    //     int  h = 1;
    //     while (h < n / 2) {
    //         h = n * 2;
    //     }
    //
    //     // 改动一，把插入排序的主要逻套在h的while循环中
    //     while (h >= 1) {
    //         // 改动二，sortedIndex初始化为h，而非1
    //         int sortedIndex = h;
    //         while (sortedIndex < n) {
    //             // 改动三，把比较和交换的步长设为h，而非相邻元素
    //             for (int i = sortedIndex; i >= h; i -= h) {
    //                 if (nums[i] < nums[i - h]) {
    //                     int temp = nums[i];
    //                     nums[i] = nums[i - h];
    //                     nums[i - h] = temp;
    //                 } else {
    //                     break;
    //                 }
    //             }
    //             sortedIndex++;
    //         }
    //
    //         // 按照递归函数的规则，缩小h
    //         h /= 2;
    //     }
    // }

    // 优化
    public void sort(int[] nums) {
        int n = nums.length;
        int h = 1;
        while (h < n / 3) {
            h = 3 * h + 1;
        }

        while (h >= 1) {
            int sortedIndex = h;
            while (sortedIndex < n) {
                for (int i = sortedIndex; i >= h; i -= h) {
                    if (nums[i] < nums[i - h]) {
                        int temp = nums[i];
                        nums[i] = nums[i - h];
                        nums[i - h] = temp;
                    }
                }
                sortedIndex++;
            }
            h /= 3;
        }
    }
}
